Outline

• Supervised learning and loss function
• Tree method and ensemble
• Gradient boosting
• Extreme gradient boosting
• xgboost R package

Supervised Learning

• Regression: Linear regression – square error loss \[l(y_i,\widehat{y})=(y_i-\widehat{y}_i)^2\]
• Classification: Logistic regression – logistic loss \[l(y_i,\widehat{y}_i)=y_i\log(1+e^{-\widehat{y}_i})+(1-y_i)\log(1+e^{\widehat{y}_i})\]
• Loss on training data: \(L=\sum_{i=1}^n l(y_i,\widehat{y}_i)\)
• Regularization: Bias-variance trade-off

Additive Training (Boosting)

• Convert a set of weak learners to a single strong learner.
• Start from a constant prediction, add a new learner each time. \[\begin{align*} \widehat{y}_i^{(0)} &=C \\ \widehat{y}_i^{(1)} &=C+f_1(x_i)=\widehat{y}_i^{(0)}+f_1(x_i) \\ \widehat{y}_i^{(2)} &=C+f_1(x_i)+f_2(x_i)=\widehat{y}_i^{(1)}+f_2(x_i) \\ &\cdots \\ \widehat{y}_i^{(t)} &=C+\sum_{k=1}^t f_t(x_i)=\widehat{y}_i^{(t-1)}+f_t(x_i) \end{align*}\]

Example: Ensemble Classification Trees

Example: Ensemble Classification Trees

Gradient Boosting Tree (Friedman)

1. Initialize a constant value model \(f_0\).
2. For \(t=1\) to \(T\), do

• Compute the gradient (pseudo-residuals) \[\widetilde{y}_i=\left.\frac{\partial}{\partial\widehat{y}_i} l(y_i,\widehat{y}_i)\right\vert_{\widehat{y}_i=\widehat{y}_i^{(t-1)}}\]
• Fit a tree \(h_t\) to the gradients.
• Line search to find the step size \(\epsilon_t\) \[\epsilon_t=\arg\min_\epsilon\sum_{i=1}^n l(y_i,\widehat{y}_i^{(t-1)}+\epsilon h_t(x_i))\]
• Update the additive model using \(f_t(x)=\epsilon_t h_t(x)\)

Extreme Gradient Boosting (Chen)

• At round \(t\), the objective function to minimize \[Obj^{(t)}=\sum_{i=1}^n l(y_i,\widehat{y}_i^{(t)})+\Omega(f_t)=\sum_{i=1}^n l(y_i,\widehat{y}_i^{(t-1)}+f_t(x_i))+\Omega(f_t)\]
• Second-order Taylor Expansion at \(\widehat{y}^{(t-1)}\) \[\begin{align*} Obj^{(t)}&\approx \sum_{i=1}^n \left(l(y_i,\widehat{y}_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t(x_i)^2\right)+\Omega(f_t) \\ &=\sum_{i=1}^n \left(g_if_t(x_i)+\frac{1}{2}h_if_t(x_i)^2\right)+\Omega(f_t)+Constant \end{align*}\]

XGBoost

• Base learner: regression tree \(f_t(x)=w_{q(x)}\), piece-wise constant
• Define tree complexity \[\Omega(f_t)=\gamma|T|+\frac{1}{2}\lambda\sum_{j=1}^{|T|}w_j^2\]
• Regroup the objective \[\begin{align*} Obj^{(t)}&\approx \sum_{i=1}^n \left(g_if_t(x_i)+\frac{1}{2}h_if_t(x_i)^2\right)+\Omega(f_t) \\ &= \sum_{i=1}^n \left(g_i w_{q(x_i)}+\frac{1}{2}h_i w_{q(x_i)}^2\right)+\gamma|T|+\frac{1}{2}\lambda\sum_{j=1}^{|T|}w_j^2 \\ &= \sum_{j=1}^{|T|} \left[\left(\sum_{i\in I_j} g_i\right)w_j+\frac{1}{2}\left(\sum_{i\in I_j} h_i+\lambda\right)w_j^2\right]+\gamma|T| \end{align*}\]

XGBoost Continued

\[Obj^{(t)}\approx \sum_{j=1}^{|T|} \left[G_jw_j+\frac{1}{2}\left(H_j+\lambda\right)w_j^2\right]+\gamma|T|\]

• If the tree structure is determined, \(w_j^*=-\frac{G_j}{H_j+\lambda}\). We only need to find a tree structure to minimize \[Obj^{(t)}\approx -\frac{1}{2}\sum_{j=1}^{|T|} \frac{G_j^2}{H_j+\lambda}+\gamma|T|\]

Searching Algorithm

• Enumerate the possible tree structures: N-P hard
• Greedy search \[\text{Gain}=\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}-\gamma\]
• Handling missing values: When using a feature with missing values to do splitting, xgboost will assign a direction to the missing values instead of a numerical value. Specifically, xgboost guides the data points with missing values to the left and right respectively, then choose the direction with a higher gain with regard to the objective.

More about XGBoost

• Post-pruning: Grow a tree to maximum depth, recursively prune splits with negative gain.
• Row subsampling; Column subsampling (random forest)
• Learning rate: step size \(\widehat{y}^{(t)}=\widehat{y}^{(t-1)}+\epsilon f_t(x)\)
  This means we do not do full optimization in each step and reserve chance for future rounds. It helps prevent overfitting.
• Customize your own loss function.
• Linear booster

xgboost R Package

xgboost(data = NULL, label = NULL, missing = NA,
                  weight = NULL, params = list(), nrounds, ...)

• data
  dense Matrix: i.e. matrix ;
  sparse Matrix: i.e. Matrix::dgCMatrix ;
  xgb.DMatrix: its own class (recommended).
• booster [default=gbtree]
  which booster to use, can be “gbtree”, “gblinear” or “dart”.
• objective [default=reg:linear]
  “reg:linear”, “reg:logistic”, “binary:logistic”, “count:poisson”, “survival:cox”, “multi:softmax”, “multi:softprob”
• nrounds
  
• eta [default=0.3, alias: learning_rate]
  
• gamma [default=0, alias: min_split_loss]

xgboost R Package

xgboost(data = NULL, label = NULL, missing = NA,
                  weight = NULL, params = list(), nrounds, ...)

• max_depth [default=6]
• subsample [default=1]
• colsample_bytree [default=1]
• colsample_bylevel [default=1]
• lambda [default=1, alias: reg_lambda]
• alpha [default=0, alias: reg_alpha]
  L1 regularization term

Example 1: Iris Data (Multi-class Classification)

df <- iris
str(df)

## 'data.frame':    150 obs. of  5 variables:
##  $ Sepal.Length: num  5.1 4.9 4.7 4.6 5 5.4 4.6 5 4.4 4.9 ...
##  $ Sepal.Width : num  3.5 3 3.2 3.1 3.6 3.9 3.4 3.4 2.9 3.1 ...
##  $ Petal.Length: num  1.4 1.4 1.3 1.5 1.4 1.7 1.4 1.5 1.4 1.5 ...
##  $ Petal.Width : num  0.2 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 ...
##  $ Species     : Factor w/ 3 levels "setosa","versicolor",..: 1 1 1 1 1 1 1 1 1 1 ...

X <- as.matrix(df[,-5])
Y <- as.numeric(df[,5]) - 1
dtrain <- xgb.DMatrix(data = X, label = Y)

Example 1

library(xgboost)
xgbtree1 <- xgboost(data = dtrain, objective = "multi:softmax", 
                   nrounds = 20, max.depth = 3, num_class = 3, eta = 0.2)

## [1]  train-merror:0.026667 
## [2]  train-merror:0.026667 
## [3]  train-merror:0.026667 
## [4]  train-merror:0.026667 
## [5]  train-merror:0.026667 
## [6]  train-merror:0.026667 
## [7]  train-merror:0.026667 
## [8]  train-merror:0.026667 
## [9]  train-merror:0.026667 
## [10] train-merror:0.026667 
## [11] train-merror:0.020000 
## [12] train-merror:0.020000 
## [13] train-merror:0.013333 
## [14] train-merror:0.013333 
## [15] train-merror:0.013333 
## [16] train-merror:0.013333 
## [17] train-merror:0.013333 
## [18] train-merror:0.013333 
## [19] train-merror:0.013333 
## [20] train-merror:0.013333

Example 1

pred1 <- predict(xgbtree1, X)
head(pred1)     # class labels

## [1] 0 0 0 0 0 0

xgbtree2 <- xgboost(data = dtrain, objective = "multi:softprob", 
                   nrounds = 20, max.depth = 3, num_class = 3, eta = 0.2, 
                   verbose = 0)
pred2 <- predict(xgbtree2, X)
head(matrix(pred2, ncol = 3, byrow = TRUE))    # class probabilities

##           [,1]       [,2]      [,3]
## [1,] 0.9757425 0.01341130 0.0108463
## [2,] 0.9762915 0.01285605 0.0108524
## [3,] 0.9762915 0.01285605 0.0108524
## [4,] 0.9762915 0.01285605 0.0108524
## [5,] 0.9757425 0.01341130 0.0108463
## [6,] 0.9757425 0.01341130 0.0108463

Example 1

tree <- xgb.dump(xgbtree2, with_stats = TRUE)
tree[1:14]    # check the first two trees

##  [1] "booster[0]"                                                  
##  [2] "0:[f2<2.45] yes=1,no=2,missing=1,gain=72.2968,cover=66.6667" 
##  [3] "1:leaf=0.287081,cover=22.2222"                               
##  [4] "2:leaf=-0.146699,cover=44.4444"                              
##  [5] "booster[1]"                                                  
##  [6] "0:[f2<2.45] yes=1,no=2,missing=1,gain=18.0742,cover=66.6667" 
##  [7] "1:leaf=-0.143541,cover=22.2222"                              
##  [8] "2:[f3<1.75] yes=3,no=4,missing=3,gain=41.9078,cover=44.4444" 
##  [9] "3:[f2<4.95] yes=5,no=6,missing=5,gain=4.58985,cover=24"      
## [10] "5:leaf=0.277612,cover=21.3333"                               
## [11] "6:leaf=-6.50233e-09,cover=2.66667"                           
## [12] "4:[f2<4.85] yes=7,no=8,missing=7,gain=0.635159,cover=20.4444"
## [13] "7:leaf=-5.10897e-09,cover=1.33333"                           
## [14] "8:leaf=-0.142541,cover=19.1111"

Example 1

xgb.plot.tree(feature_names = dimnames(dtrain)[[2]], model = xgbtree2, 
              n_first_tree = 1, plot_width = 1000, plot_height = 500)

Example 1

importance <- xgb.importance(feature_names = dimnames(dtrain)[[2]], 
                             model = xgbtree2)
xgb.ggplot.importance(importance) + theme(legend.position="none")

Example 1

xgb.save(xgbtree2, "xgbtree.model")     # save the final model

## [1] TRUE

xgbtree3 <- xgb.load("xgbtree.model")   # load the saved model 

Tuning: Cross Validation

xgb.cv(..., nfold, metrics = list(),
                early_stopping_rounds = NULL, ...)

• nfold
• metrics
  Evaluation metrics for validation data, a default metric will be assigned according to objective.
  
• early_stopping_rounds
  If the performance is not getting better for this number of steps, the program will stop.

Tuning: Validation Set

xgboost(data = NULL, label = NULL, missing = NA,
                  weight = NULL, params = list(), nrounds, ...)

• watchlist
  It is a list of xgb.DMatrix objects, each of them tagged with a name.

Example 2: UCI Adult (Binary Classification)

Reference and Resources

• Tianqi Chen & Carlos Guestrin (2016). XGBoost: A Scalable Tree Boosting System. CoRR, abs/1603.02754, .
• Friedman, J. (2001). Greedy Function Approximation: A Gradient Boosting Machine. The Annals of Statistics, 29(5), 1189-1232.
• Introduction to Boosted Trees, Tianqi Chen, homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf.
• Awesome XGBoost
• XGBoost R Tutorial
• Introduction to Parameters
• The Github Repository of XGBoost